|
|- | An example of Bélády's anomaly. Using three page frames, 9 page faults occur. Increasing to four page frames causes 10 page faults to occur. Page faults are in red. |} In computer storage, Bélády's anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern. This phenomenon is commonly experienced when using the First in First Out (FIFO) page replacement algorithm. László Bélády demonstrated this in 1969. In common computer memory management, information is loaded in specific sized chunks. Each chunk is referred to as a ''page''. The central processor can only hold a limited number of pages at a time. It requires a ''frame'' for each page it can load. A ''page fault'' occurs when a page is not found, and might need to be loaded from disk into memory. When a page fault occurs and all frames are in use, one must be cleared to make room for the new page. A simple algorithm is FIFO: whichever page has been in the frames the longest is the one that is cleared. Until Bélády's anomaly was demonstrated, it was believed that an increase in the number of page frames would always result in the same number or fewer page faults. ==Bélády's anomaly is unbounded== Bélády, Nelson and Shedler constructed reference strings for which FIFO page replacement algorithm produced nearly twice more page faults in a larger memory than in a smaller one and they formulated the conjecture that 2 is a general bound. In 2010, Fornai and Iványi showed that the anomaly is in fact unbounded and that one can construct a reference string to any arbitrary page fault ratio. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bélády's anomaly」の詳細全文を読む スポンサード リンク
|